package algorithm.dp;

import java.util.Arrays;

// 下降路径最小和
public class LC931 {
    public int minFallingPathSum(int[][] matrix) {
        // 1. 创建 dp 表
        int m = matrix.length, n = matrix.length;
        int[][] dp = new int[m+1][n+2];

        // 2. 初始化 -> 第一行全为 0, 后面全部为 100
        for (int i = 1; i < dp.length; i++)
            dp[i][0] = dp[i][n+1] = Integer.MAX_VALUE;

        // 3. 填表
        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= n; j++)
                dp[i][j] =
                        Math.min(dp[i-1][j-1], Math.min(dp[i-1][j], dp[i-1][j+1])) +
                                matrix[i-1][j-1];
        int ans = Integer.MAX_VALUE;
        for (int i = 1; i <= n; i++)
            ans = Math.min(ans, dp[m][i]);
        return ans;
    }

    public static void main(String[] args) {
        LC931 lc931 = new LC931();
        int[][] matrix = {{-19, 57}, {-40, -5}};
        lc931.minFallingPathSum(matrix);
    }
}
